Extensions of Fractional Precolorings Show Discontinuous Behavior. Issue 4 (13th February 2014)

• Record Type: Journal Article
• Authors: van den Heuvel, Jan; Král', Daniel; Kupec, Martin; Sereni, Jean‐Sébastien; Volec, Jan
• Is Part Of: Journal of graph theory. Volume 77:Issue 4(2014)
• Page Start: 299
• Page End: 329
• Publication Date: 2014-02-13
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21787
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>We study the following problem: given a real number <italic>k</italic> and an integer <italic>d</italic>, what is the smallest ε such that any fractional <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d0p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>ɛ</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐precoloring of vertices at pairwise distances at least <italic>d</italic> of a fractionally <italic>k</italic>‐colorable graph can be extended to a fractional <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d17" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>ɛ</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐coloring of the whole graph? The exact values of ε were known for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11cx2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>∈</mml:mo><mml:mo>{</mml:mo><mml:mn>2</mml:mn><mml:mo>}</mml:mo><mml:mo>∪</mml:mo><mml:mo>[</mml:mo><mml:mn>3</mml:mn><mml:mo>, </mml:mo><mml:mi>∞</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> and any <italic>d</italic>. We determine the exact values of ε for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11czm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>∈</mml:mo><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mo>, </mml:mo><mml:mn>3</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> if <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d4w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>, and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d5f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mn>2.5</mml:mn><mml:mo>, </mml:mo><mml:mn>3</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> if <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d2s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>, and give upper bounds for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d3b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>∈</mml:mo><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mo>, </mml:mo><mml:mn>3</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> if <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11d9n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>5</mml:mn><mml:mo>, </mml:mo><mml:mn>7</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>, and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11jk4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>∈</mml:mo><mml:mo>(</mml:mo><mml:mn>2</mml:mn><mml:mo>, </mml:mo><mml:mn>2.5</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> if <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh1fd11jmp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21787:jgt21787-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. Surprisingly, ε viewed as a function of <italic>k</italic> is discontinuous for all those values of <italic>d</italic>.</p> </abstract>