A Brooks‐Type Theorem for the Bichromatic Number. Issue 4 (23rd December 2014)

• Record Type: Journal Article
• Authors: Epple, Dennis D. A.; Huang, Jing
• Is Part Of: Journal of graph theory. Volume 80:Issue 4(2015)
• Page Start: 277
• Page End: 286
• Publication Date: 2014-12-23
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21850
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A classical theorem of Brooks in graph coloring theory states that every connected graph <italic>G</italic> has its chromatic number <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp421fr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>χ</mml:mi><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> less than or equal to its maximum degree <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp421mb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>Δ</mml:mi><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, unless <italic>G</italic> is a complete graph or an odd cycle in which case <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp421j9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>χ</mml:mi><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> is equal to <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp4226m" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>Δ</mml:mi><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. Brooks' theorem has been extended to list colorings by Erdős, Rubin, and Taylor (and, independently, by Vizing) and to some of their variants such as list <italic>T</italic>‐colorings and pair‐list colorings. The bichromatic number is a relatively new parameter arisen in the study of extremal hereditary properties of graphs. This parameter simultaneously generalizes the chromatic number and the clique covering number of a graph.</p> <p>In this article, we prove a theorem, akin to that of Brooks, which states that every graph <italic>G</italic> has its bichromatic number <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp4228n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>χ</mml:mi><mml:mi>b</mml:mi></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula> less than or equal to its bidegree <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp422c6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>Δ</mml:mi><mml:mi>b</mml:mi></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula>, unless <italic>G</italic> belongs to a set of specified graphs in which case <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp422gr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>χ</mml:mi><mml:mi>b</mml:mi></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula> is equal to <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkfp422js" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21850:jgt21850-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>Δ</mml:mi><mml:mi>b</mml:mi></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>.</p> </abstract>