Scheinermans gissning

Inom matematiken säger Scheinermans gissning , nu en sats, att varje plan graf är skärningsdiagrammet för en uppsättning linjesegment i planet. Denna gissning formulerades av ER Scheinerman i sin Ph.D. avhandling (1984) , efter tidigare resultat att varje plan graf kunde representeras som skärningsgrafen för en uppsättning enkla kurvor i planet ( Ehrlich, Even & Tarjan 1976) . Det bevisades av Jeremie Chalopin och Daniel Gonçalves ( 2009 ).

Till exempel kan grafen G som visas nedan till vänster representeras som skärningsdiagrammet för uppsättningen av segment som visas nedan till höger. Här representeras hörn av G av raka linjesegment och kanter av G representeras av skärningspunkter.

 

Scheinerman antog också att segment med endast tre riktningar skulle vara tillräckligt för att representera 3- färgbara grafer, och West (1991) antog att analogt varje plan graf kunde representeras med fyra riktningar. Om en graf representeras med segment som endast har k riktningar och inga två segment hör till samma linje, kan grafen färgläggas med k färger, en färg för varje riktning. Därför, om varje plan graf kan representeras på detta sätt med endast fyra riktningar, så följer fyrafärgssatsen .

Hartman, Newman & Ziv (1991) och de Fraysseix, Ossona de Mendez & Pach (1991) bevisade att varje tvådelad plan graf kan representeras som en skärningsgraf av horisontella och vertikala linjesegment; för detta resultat se även Czyzowicz, Kranakis & Urrutia (1998) . De Castro et al. (2002) bevisade att varje triangelfri plan graf kan representeras som en skärningsgraf av linjesegment som endast har tre riktningar; detta resultat antyder Grötzschs teorem ( Grötzsch 1959 ) att triangelfria plana grafer kan färgas med tre färger. de Fraysseix & Ossona de Mendez (2005) bevisade att om en plan graf G kan vara 4-färgad på ett sådant sätt att ingen separeringscykel använder alla fyra färgerna, så har G en representation som en skärningsgraf av segment.

Chalopin, Gonçalves & Ochem (2007) bevisade att plana grafer är i 1-STRING, klassen av skärningsgrafer för enkla kurvor i planet som skär varandra i högst en korsningspunkt per par. Denna klass är mellanliggande mellan skärningsgraferna för segment som förekommer i Scheinermans gissning och skärningsgraferna för obegränsade enkla kurvor från resultatet av Ehrlich et al. Det kan också ses som en generalisering av cirkelpackningssatsen , som visar samma resultat när kurvor tillåts skära i en tangent. Beviset för gissningen av Chalopin & Gonçalves (2009) baserades på en förbättring av detta resultat.

•   De Castro, N.; Cobos, FJ; Dana, JC; Márquez, A. (2002), "Triangel-free planar graphs as segment intersection graphs" (PDF) , Journal of Graph Algorithms and Applications , 6 (1): 7–26, doi : 10.7155/jgaa.00043 , MR 1898201 .
• Chalopin, J.; Gonçalves, D. (2009), "Varje plan graf är skärningsdiagrammet för segment i planet" ( PDF) , ACM Symposium on Theory of Computing .
• Chalopin, J.; Gonçalves, D.; Ochem, P. (2007), "Planar graphs are in 1-STRING", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms , ACM and SIAM, s. 609–617 .
• Czyzowicz, J.; Kranakis, E.; Urrutia, J. (1998), "Ett enkelt bevis på representationen av tvådelade plana grafer som kontaktgraferna för ortogonala raka linjesegment", Information Processing Letters , 66 (3): 125–126, doi : 10.1016/S0020-0190 (98)00046-5 .
• de Fraysseix, H.; Ossona de Mendez, P. (2005), "Contact and intersection representations", i Pach, J. (red.), Graph Drawing, 12th International Symposium, GD 2004 , Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, s. 217–227 .
•   de Fraysseix, H.; Ossona de Mendez, P. ; Pach, J. (1991), "Representation of planar graphs by segments", Intuitive Geometry , 63 : 109-117, MR 1383616 .
•   Ehrlich, G.; Even, S.; Tarjan, RE (1976), "Skärningsdiagram över kurvor i planet", Journal of Combinatorial Theory , Series B, 21 (1): 8–20, doi : 10.1016/0095-8956(76)90022-8 , MR 0505857 .
•   Grötzsch, Herbert (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe , 8 : 109–120, MR 0116320 .
•   Hartman, IB-A.; Newman, I.; Ziv, R. (1991), "On grid intersection graphs", Discrete Mathematics , 87 (1): 41–52, doi : 10.1016/0012-365X(91)90069-E , MR 1090188 .
• Scheinerman, ER (1984), Intersection Classes and Multiple Intersection Parameters of Graphs, Ph.D. avhandling, Princeton University .
• West, D. (1991), "Öppna problem #2", SIAM Activity Group Newsletter in Discrete Mathematics , 2 (1): 10–12 .