请输入您要查询的百科知识：

　

词条 Χ-bounded
释义

  1. Nontriviality

  2. Specific classes

  3. Unsolved problems

  4. References

  5. External links

{{DISPLAYTITLE:χ-bounded}}

In graph theory, a -bounded family of graphs is one for which there is some function such that, for every integer the graphs in with no -vertex clique can be colored with at most colors. This concept and its notation were formulated by András Gyárfás.{{r|g87}} The use of the Greek letter chi in the term -bounded is based on the fact that the chromatic number of a graph is commonly denoted .

Nontriviality

It is not true that the family of all graphs is -bounded.

As {{harvtxt|Zykov|1949}} and {{harvtxt|Mycielski|1955}} showed, there exist triangle-free graphs of arbitrarily large chromatic number,{{r|z|m}} so for these graphs it is not possible to define a finite value of .

Thus, -boundedness is a nontrivial concept, true for some graph families and false for others.{{r|pkk}}

Specific classes

Every class of graphs of bounded chromatic number is (trivially) -bounded, with equal to the bound on the chromatic number. This includes, for instance, the planar graphs, the bipartite graphs, and the graphs of bounded degeneracy. Complementarily, the graphs in which the independence number is bounded are also -bounded, as Ramsey's theorem implies that they have large cliques.

Vizing's theorem can be interpreted as stating that the line graphs are -bounded, with .{{r|cs|km}} The claw-free graphs more generally are also -bounded with . This can be seen by using Ramsey's theorem to show that, in these graphs, a vertex with many neighbors must be part of a large clique.

This bound is nearly tight in the worst case, but connected claw-free graphs that include three mutually-nonadjacent vertices have even smaller chromatic number, .{{r|cs}}

Other -bounded graph families include:

  • The perfect graphs, with
  • The graphs of boxicity two{{r|ag60}}
  • The graphs of bounded clique-width{{r|dk12}}
  • The intersection graphs of scaled and translated copies of any compact convex shape in the plane{{r|kkn04}}
  • The circle graphs, and (generalizing circle graphs) the "outerstring graphs", intersection graphs of bounded curves in the plane that all touch the unbounded face of the arrangement of the curves{{r|rw14}}

However, although intersection graphs of convex shapes, circle graphs, and outerstring graphs are all special cases of string graphs, the string graphs themselves are not -bounded.

They include as a special case the intersection graphs of line segments, which are also not -bounded.{{r|pkk}}

Unsolved problems

{{unsolved|mathematics|Are all tree-free graph classes -bounded?}}

According to the Gyárfás–Sumner conjecture, for every tree , the graphs that do not contain as an induced subgraph are -bounded.

For instance, this would include the case of claw-free graphs, as a claw is a special kind of tree.

However, the conjecture is known to be true only for certain special trees, including paths{{r|g87}} and radius-two trees.{{r|kp94}}

Another unsolved problem on -bounded was posed by Louis Esperet, who asked whether every hereditary class of graphs that is -bounded has a function that grows at most polynomially as a function of .{{r|km}}

{{unsolved|mathematics|In a hereditary -bounded graph class, is the chromatic number at most polynomial in the clique size?}}

References

1. ^{{citation | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | issue = 6 | journal = Journal of Combinatorial Theory | mr = 2718677 | pages = 560–572 | series = Series B | title = Claw-free graphs VI. Colouring | doi = 10.1016/j.jctb.2010.04.005 | volume = 100 | year = 2010}}
2. ^{{citation | last1 = Dvořák | first1 = Zdeněk | last2 = Král' | first2 = Daniel | arxiv = 1107.2161 | doi = 10.1016/j.ejc.2011.12.005 | issue = 4 | journal = Electronic Journal of Combinatorics | mr = 3350076 | pages = 679–683 | title = Classes of graphs with small rank decompositions are -bounded | volume = 33 | year = 2012}}
3. ^{{citation | last = Gyárfás | first = A. | authorlink = András Gyárfás | department = Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985) | issue = 3-4 | journal = Zastosowania Matematyki | mr = 951359 | pages = 413–441 (1988) | title = Problems from the world surrounding perfect graphs | volume = 19 | year = 1987}}
4. ^{{citation | last1 = Kim | first1 = Seog-Jin | last2 = Kostochka | first2 = Alexandr | last3 = Nakprasit | first3 = Kittikorn | issue = 1 | journal = Electronic Journal of Combinatorics | mr = 2097318 | at = R52 | title = On the chromatic number of intersection graphs of convex sets in the plane | url = http://www.combinatorics.org/Volume_11/Abstracts/v11i1r52.html | volume = 11 | year = 2004}}
5. ^{{citation | last1 = Kierstead | first1 = H. A. | last2 = Penrice | first2 = S. G. | issue = 2 | journal = Journal of Graph Theory | mr = 1258244 | pages = 119–129 | title = Radius two trees specify -bounded classes | doi = 10.1002/jgt.3190180203 | volume = 18 | year = 1994}}
6. ^{{citation | last1 = Karthick | first1 = T. | last2 = Maffray | first2 = Frédéric | doi = 10.1007/s00373-015-1651-1 | issue = 4 | journal = Graphs and Combinatorics | mr = 3514976 | pages = 1447–1460 | title = Vizing bound for the chromatic number on some graph classes | volume = 32 | year = 2016}}
7. ^{{citation | last = Mycielski | first = Jan | authorlink = Jan Mycielski | title = Sur le coloriage des graphs | journal = Colloq. Math. | language = French | volume = 3 | year = 1955 | pages = 161–162 | mr = 0069494}}
8. ^{{citation | last1 = Pawlik | first1 = Arkadiusz | last2 = Kozik | first2 = Jakub | last3 = Krawczyk | first3 = Tomasz | last4 = Lasoń | first4 = Michał | last5 = Micek | first5 = Piotr | last6 = Trotter | first6 = William T. | author6-link = William T. Trotter | last7 = Walczak | first7 = Bartosz | doi = 10.1016/j.jctb.2013.11.001 | journal = Journal of Combinatorial Theory | mr = 3171778 | pages = 6–10 | series = Series B | title = Triangle-free intersection graphs of line segments with large chromatic number | volume = 105 | year = 2014| arxiv = 1209.1595}}
9. ^{{citation | last1 = Rok | first1 = Alexandre | last2 = Walczak | first2 = Bartosz | contribution = Outerstring graphs are -bounded | doi = 10.1145/2582112.2582115 | mr = 3382292 | pages = 136–143 | publisher = ACM | location = New York | title = Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SoCG'14) | year = 2014}}
10. ^{{citation | last = Zykov | first = A. A. | issue = 66 | journal = Mat. Sbornik N.S. | language = Russian | mr = 0035428 | pages = 163–188 | title = О некоторых свойствах линейных комплексов | trans-title = On some properties of linear complexes | url = http://mi.mathnet.ru/msb5974 | volume = 24 | year = 1949}}. Translated into English in Amer. Math. Soc. Translation, 1952, {{MR|0051516}}. As cited by {{harvtxt|Pawlik|Kozik|Krawczyk|Lasoń|2014}}
[1][2][3][4][5][6][7][8][9][10]
}}

External links

  • Chi-bounded, Open Problem Garden

1 : Graph coloring
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/14 3:07:10