Triangle-free graph

Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

By Turán's theorem, the "n"-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.

It is possible to test whether a graph with "m" edges is triangle-free in time O("m"1.41) (Alon et al. 1994). As Imrich et al. (1999) show, triangle-free graph recognition is equivalent in complexity to median graph recognition; however, the current best algorithms for median graph recognition use triangle detection as a subroutine rather than vice versa.

Coloring triangle-free graphs

Much research about triangle-free graphs has focused on graph coloring. Every bipartite graph (that is, every 2-colorable graph) is triangle-free, and Grötzsch's theorem states that every triangle-free planar graph may be 3-colored (Grötzsch 1959; Thomassen 1994). However, nonplanar triangle-free graphs may require many more than three colors.

Mycielski (1955) defined a construction, now called the Mycielskian, for forming a new triangle-free graph from another triangle-free graph. If a graph has chromatic number "k", its Mycielskian has chromatic number "k"+1, so this construction may be used to show that arbitrarily large numbers of colors may be needed to color nonplanar triangle-free graphs. In particular the Grötzsch graph, an 11-vertex graph formed by repeated application of Mycielski's construction, is a triangle-free graph that cannot be colored with fewer than four colors, and is the smallest graph with this property (Chvátal 1974). Nilli (2000) showed that the number of colors needed to color any "m"-edge triangle-free graph is:O left(frac{m^{1/3{(log m)^{2/3 ight)and that there exist triangle-free graphs that have chromatic numbers proportional to this bound.

There have also been several results relating coloring to minimum degree in triangle-free graphs.Andrásfai et al (1974) proved that any "n"-vertex triangle-free graph in which each vertex has more than 2"n"/5 neighbors must be bipartite.This is the best possible result of this type, as the 5-cycle requires three colors but has exactly 2"n"/5 neighbors per vertex.Motivated by this result, Paul Erdős and M. Simonovits (1973) conjectured that any "n"-vertex triangle-free graph in which each vertex has at least "n"/3 neighbors can be colored with only three colors; however, Häggkvist (1981) disproved this conjecture by finding a counterexample in which each vertex of the Grötzsch graph is replaced by an independent set of a carefully chosen size. Jin (1995) showed that any "n"-vertex triangle-free graph in which each vertex has more than 10"n"/29 neighbors must be 3-colorable; this is the best possible result of this type. Finally, Brandt and Thomassé (unpublished as of 2006) proved that any "n"-vertex triangle-free graph in which each vertex has more than "n"/3 neighbors must be 4-colorable. Additional results of this type are not possible, as Hajnal (see Erdős and Simonovits 1973) found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3-ε)"n" for any ε > 0.

References


*cite conference
author = Alon, N.; Yuster, R.; Zwick, U.
title = Finding and counting given length cycles
booktitle = Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands
pages = 354–364
date = 1994

*cite journal
author = Andrásfai, B.; Erdős, P.; Sós, V. T.
title = On the connection between chromatic number, maximal clique and minimal degree of a graph
journal = Discrete Mathematics
volume = 8
year = 1974
pages = 205–218
doi = 10.1016/0012-365X(74)90133-2

*cite web
author = Brandt, S.; Thomassé, S.
title = Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem
url = http://www.lirmm.fr/~thomasse/liste/vega11.pdf

*cite journal
author = Chiba, N.; Nishizeki, T.
title = Arboricity and subgraph listing algorithms
journal = SIAM J. Comput.
volume = 14
year = 1985
pages = 210–223
doi = 10.1137/0214017

*cite conference
author = Chvátal, Vašek
title = The minimality of the Mycielski graph
booktitle = Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973)
date = 1974
pages = 243–246
publisher = Lecture Notes in Mathematics, Vol. 406, Springer-Verlag
location = Berlin

*cite journal
author = Erdős, P.; Simonovits, M.
title = On a valence problem in extremal graph theory
journal = Discrete Mathematics
volume = 5
year = 1973
pages = 323–334
doi = 10.1016/0012-365X(73)90126-X

*cite journal
author = Grötzsch, H.
title = Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel
journal = Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe
volume = 8
year = 1959
pages = 109–120

*cite conference
author = Häggkvist, R.
title = Odd cycles of specified length in nonbipartite graphs
booktitle = Graph Theory (Cambridge, 1981)
date = 1981
pages = 89–99

*citation
last1 = Imrich | first1 = Wilfried | last2 = Klavžar | first2 = Sandi
last3 = Mulder | first3 = Henry Martyn
title = Median graphs and triangle-free graphs
journal = SIAM Journal on Discrete Mathematics
volume = 12 | issue = 1 | pages = 111–118 | year = 1999
id = MathSciNet | id = 1666073
doi = 10.1137/S0895480197323494
.

*cite journal
title = Finding a minimum circuit in a graph
author = Itai, A.; Rodeh, M.
journal = SIAM J. Comput.
volume = 7
year = 1978
pages = 413–423
doi = 10.1137/0207033

*cite journal
author = Jin, G.
title = Triangle-free four-chromatic graphs
journal = Discrete Mathematics
volume = 145
year = 1995
pages = 151–170
doi = 10.1016/0012-365X(94)00063-O

*cite journal
author = Mycielski, J.
title = Sur le coloriage des graphes
journal = Colloq. Math.
volume = 3
year = 1955
pages = 161–162

*cite journal
author = Nilli, A.
title = Triangle-free graphs with large chromatic numbers
journal = Discrete Mathematics
volume = 211
year = 2000
issue = 1–3
pages = 261–262
doi = 10.1016/S0012-365X(99)00109-0

*cite journal
title = Note on the independence number of triangle-free graphs
author = Shearer, J. B.
journal = Discrete Mathematics
volume = 46
issue = 1
pages = 83–87
year = 1983
doi = 10.1016/0012-365X(83)90273-X

*cite journal
author = Thomassen, C.
title = Grötzsch's 3-color theorem
journal = Journal of Combinatorial Theory, Series B
volume = 62
year = 1994
pages = 268–279
doi = 10.1006/jctb.1994.1069

External links

* cite web | url=http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_371.html | title=triangle-free
work = [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia

  • Grötzsch graph — infobox graph name = Grötzsch graph namesake = Herbert Grötzsch vertices = 11 edges = 20 chromatic number = 4 chromatic index = girth = 4 properties = The Grötzsch graph is a triangle free graph with 11 vertices, 20 edges, and chromatic number 4 …   Wikipedia

  • Chvátal graph — Named after Václav Chvátal Vertices 12 Edges 24 …   Wikipedia

  • Clebsch graph — Named after Alfred Clebsch Vertices 16 Edges 40 …   Wikipedia

  • Intersection number (graph theory) — In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover… …   Wikipedia

  • Outerplanar graph — A maximal outerplanar graph and its 3 coloring. In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing.… …   Wikipedia

  • Complement graph — The Petersen graph (on the left) and its complement graph (on the right). In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”