6 papers
Nowhere-zero 4-flows in graphs excluding a proper minor of the Petersen graph
József Pintér, József Pintér
Tutte's -flow conjecture asserts that every finite bridgeless graph with no Petersen minor admits a nowhere-zero -flow. Let be the Petersen graph and let . We…
The crumby coloring conjecture for subcubic outerplanar graphs
József Pintér
The red-blue vertex partitions now known as crumby colorings originate in a conjecture of Thomassen related to Wegner's conjecture on squares of planar graphs. In such a coloring,…
Conformability is NP-complete, even on connected regular graphs
József Pintér
A graph is conformable if it admits a proper -coloring in which, among the color classes including the empty ones, at most …
Subcubic -minor-free graphs without crumby colorings
József Pintér
Motivated by Wegner's conjecture on squares of planar graphs, Thomassen conjectured that every 3-connected cubic graph on at least eight vertices admits a red-blue vertex coloring…
Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
József Pintér, Regina Stangl
Network caching asks how to place contents in distributed caches so that future requests are served close to their users. Ganian, Mc Inerney and Tsigkari recently initiated the par…
Color-avoiding connected colorings and orientations
József Pintér, Kitti Varga
We study network robustness under correlated failures modeled by colors, where each color represents a class of edges or vertices that may fail simultaneously. An edge-colored grap…