2‐Distance Coloring of Sparse Graphs. Issue 3 (27th February 2014)

• Record Type: Journal Article
• Authors: Bonamy, Marthe; Lévêque, Benjamin; Pinlou, Alexandre
• Is Part Of: Journal of graph theory. Volume 77:Issue 3(2014)
• Page Start: 190
• Page End: 218
• Publication Date: 2014-02-27
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21782
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>For graphs of bounded maximum average degree, we consider the problem of 2‐distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. We prove that graphs with maximum average degree less than <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwsb7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mn>7</mml:mn><mml:mn>3</mml:mn></mml:mfrac></mml:math></alternatives></inline-formula> and maximum degree Δ at least 4 are 2‐distance <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwsdb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>Δ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We also prove that graphs with maximum average degree less than <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwscs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mn>12</mml:mn><mml:mn>5</mml:mn></mml:mfrac></mml:math></alternatives></inline-formula> (resp. <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwsgf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mn>5</mml:mn><mml:mn>2</mml:mn></mml:mfrac></mml:math></alternatives></inline-formula>, <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwsfw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mn>18</mml:mn><mml:mn>7</mml:mn></mml:mfrac></mml:math></alternatives></inline-formula>) and maximum degree Δ at least 5 (resp. 6, 8) are list 2‐distance <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwrhg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>Δ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐colorable, which improves previous results from Borodin et al., and from Ivanova. We prove that any graph with maximum average degree <italic>m</italic> less than <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwrj1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mn>14</mml:mn><mml:mn>5</mml:mn></mml:mfrac></mml:math></alternatives></inline-formula> and with large enough maximum degree Δ (depending only on <italic>m</italic>) can be list 2‐distance <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwrkk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>Δ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than 3 that cannot be 2‐distance <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwrnp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>Δ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐colored: the question of what happens between <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwpvz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mn>14</mml:mn><mml:mn>5</mml:mn></mml:mfrac></mml:math></alternatives></inline-formula> and 3 remains open. We prove also that any graph with maximum average degree <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwpp6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>m</mml:mi><mml:mo><</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> can be list 2‐distance <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwpsv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>Δ</mml:mi><mml:mo>+</mml:mo><mml:mi>C</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐colored (<italic>C</italic> depending only on <italic>m</italic>). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than 4 that cannot be 2‐distance colored with less than <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh177mwpm3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21782:jgt21782-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mrow><mml:mn>3</mml:mn><mml:mi>Δ</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:mfrac></mml:math></alternatives></inline-formula> colors. Most of the above results can be transposed to injective list coloring with one color less.</p> </abstract>