Coloring Properties of Mixed Cycloids

In this paper, we investigate partitions of highly symmetrical discrete structures called cycloids. In general, a mixed hypergraph has two types of hyperedges. The vertices are colored in such a way that each C-edge has two vertices of the same color, and each D-edge has two vertices of distinct col...

Full description

Saved in:
Bibliographic Details
Published in:Symmetry (Basel) 2021-08, Vol.13 (8), p.1539
Main Authors: Dósa, György, Newman, Nicholas, Tuza, Zsolt, Voloshin, Vitaly
Format: Article
Language:English
Subjects:
Algorithms
Apexes
circular hypergraph
Color
coloring
Cycloids
Graph coloring
Graph theory
Graphs
mixed hypergraph
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c364t-9de8a45e6c9e7687465eea97f26a2a18929240198ee4884de8bfd422a811eb883
cites cdi_FETCH-LOGICAL-c364t-9de8a45e6c9e7687465eea97f26a2a18929240198ee4884de8bfd422a811eb883
container_end_page
container_issue 8
container_start_page 1539
container_title Symmetry (Basel)
container_volume 13
creator Dósa, György
Newman, Nicholas
Tuza, Zsolt
Voloshin, Vitaly
description In this paper, we investigate partitions of highly symmetrical discrete structures called cycloids. In general, a mixed hypergraph has two types of hyperedges. The vertices are colored in such a way that each C-edge has two vertices of the same color, and each D-edge has two vertices of distinct colors. In our case, a mixed cycloid is a mixed hypergraph whose vertices can be arranged in a cyclic order, and every consecutive p vertices form a C-edge, and every consecutive q vertices form a D-edge in the ordering. We completely determine the maximum number of colors that can be used for any p≥3 and any q≥2. We also develop an algorithm that generates a coloring with any number of colors between the minimum and maximum. Finally, we discuss the colorings of mixed cycloids when the maximum number of colors coincides with its upper bound, which is the largest cardinality of a set of vertices containing no C-edge.
doi_str_mv 10.3390/sym13081539
format article
fullrecord <record><control><sourceid>proquest_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_3e3b6d2f80d44234b8d7d1f4db2a841f</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_3e3b6d2f80d44234b8d7d1f4db2a841f</doaj_id><sourcerecordid>2565715215</sourcerecordid><originalsourceid>FETCH-LOGICAL-c364t-9de8a45e6c9e7687465eea97f26a2a18929240198ee4884de8bfd422a811eb883</originalsourceid><addsrcrecordid>eNpNkM1LAzEQxYMoWGpP_gML4klW8zHJJkdZ_ChU9KDnkN1MypZtU5MW7H_v6op0LjM8Hr95PEIuGb0VwtC7fFgzQTWTwpyQCaeVKLUxcHp0n5NZzis6jKQSFJ2Q6zr2MXWbZfGW4hbTrsNcxFC8dF_oi_rQ9rHz-YKcBddnnP3tKfl4fHivn8vF69O8vl-UrVCwK41H7UCiag1WSlegJKIzVeDKcce04YYDZUYjgtYwuJvggXOnGcNGazEl85Hro1vZberWLh1sdJ39FWJaWjdEbHu0AkWjPA-aegAuoNG-8iyAbwYcsDCwrkbWNsXPPeadXcV92gzxLZdKVkzyoaopuRldbYo5Jwz_Xxm1P7Xao1rFNxVeZ_w</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2565715215</pqid></control><display><type>article</type><title>Coloring Properties of Mixed Cycloids</title><source>ProQuest - Publicly Available Content Database</source><creator>Dósa, György ; Newman, Nicholas ; Tuza, Zsolt ; Voloshin, Vitaly</creator><creatorcontrib>Dósa, György ; Newman, Nicholas ; Tuza, Zsolt ; Voloshin, Vitaly</creatorcontrib><description>In this paper, we investigate partitions of highly symmetrical discrete structures called cycloids. In general, a mixed hypergraph has two types of hyperedges. The vertices are colored in such a way that each C-edge has two vertices of the same color, and each D-edge has two vertices of distinct colors. In our case, a mixed cycloid is a mixed hypergraph whose vertices can be arranged in a cyclic order, and every consecutive p vertices form a C-edge, and every consecutive q vertices form a D-edge in the ordering. We completely determine the maximum number of colors that can be used for any p≥3 and any q≥2. We also develop an algorithm that generates a coloring with any number of colors between the minimum and maximum. Finally, we discuss the colorings of mixed cycloids when the maximum number of colors coincides with its upper bound, which is the largest cardinality of a set of vertices containing no C-edge.</description><identifier>ISSN: 2073-8994</identifier><identifier>EISSN: 2073-8994</identifier><identifier>DOI: 10.3390/sym13081539</identifier><language>eng</language><publisher>Basel: MDPI AG</publisher><subject>Algorithms ; Apexes ; circular hypergraph ; Color ; coloring ; Cycloids ; Graph coloring ; Graph theory ; Graphs ; mixed hypergraph ; Upper bounds</subject><ispartof>Symmetry (Basel), 2021-08, Vol.13 (8), p.1539</ispartof><rights>2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c364t-9de8a45e6c9e7687465eea97f26a2a18929240198ee4884de8bfd422a811eb883</citedby><cites>FETCH-LOGICAL-c364t-9de8a45e6c9e7687465eea97f26a2a18929240198ee4884de8bfd422a811eb883</cites><orcidid>0000-0001-7692-0039 ; 0000-0002-4909-6694 ; 0000-0003-3235-9221</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2565715215/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2565715215?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>314,780,784,25753,27924,27925,37012,44590,75126</link.rule.ids></links><search><creatorcontrib>Dósa, György</creatorcontrib><creatorcontrib>Newman, Nicholas</creatorcontrib><creatorcontrib>Tuza, Zsolt</creatorcontrib><creatorcontrib>Voloshin, Vitaly</creatorcontrib><title>Coloring Properties of Mixed Cycloids</title><title>Symmetry (Basel)</title><description>In this paper, we investigate partitions of highly symmetrical discrete structures called cycloids. In general, a mixed hypergraph has two types of hyperedges. The vertices are colored in such a way that each C-edge has two vertices of the same color, and each D-edge has two vertices of distinct colors. In our case, a mixed cycloid is a mixed hypergraph whose vertices can be arranged in a cyclic order, and every consecutive p vertices form a C-edge, and every consecutive q vertices form a D-edge in the ordering. We completely determine the maximum number of colors that can be used for any p≥3 and any q≥2. We also develop an algorithm that generates a coloring with any number of colors between the minimum and maximum. Finally, we discuss the colorings of mixed cycloids when the maximum number of colors coincides with its upper bound, which is the largest cardinality of a set of vertices containing no C-edge.</description><subject>Algorithms</subject><subject>Apexes</subject><subject>circular hypergraph</subject><subject>Color</subject><subject>coloring</subject><subject>Cycloids</subject><subject>Graph coloring</subject><subject>Graph theory</subject><subject>Graphs</subject><subject>mixed hypergraph</subject><subject>Upper bounds</subject><issn>2073-8994</issn><issn>2073-8994</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><sourceid>DOA</sourceid><recordid>eNpNkM1LAzEQxYMoWGpP_gML4klW8zHJJkdZ_ChU9KDnkN1MypZtU5MW7H_v6op0LjM8Hr95PEIuGb0VwtC7fFgzQTWTwpyQCaeVKLUxcHp0n5NZzis6jKQSFJ2Q6zr2MXWbZfGW4hbTrsNcxFC8dF_oi_rQ9rHz-YKcBddnnP3tKfl4fHivn8vF69O8vl-UrVCwK41H7UCiag1WSlegJKIzVeDKcce04YYDZUYjgtYwuJvggXOnGcNGazEl85Hro1vZberWLh1sdJ39FWJaWjdEbHu0AkWjPA-aegAuoNG-8iyAbwYcsDCwrkbWNsXPPeadXcV92gzxLZdKVkzyoaopuRldbYo5Jwz_Xxm1P7Xao1rFNxVeZ_w</recordid><startdate>20210801</startdate><enddate>20210801</enddate><creator>Dósa, György</creator><creator>Newman, Nicholas</creator><creator>Tuza, Zsolt</creator><creator>Voloshin, Vitaly</creator><general>MDPI AG</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SR</scope><scope>7U5</scope><scope>8BQ</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>H8D</scope><scope>HCIFZ</scope><scope>JG9</scope><scope>JQ2</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>DOA</scope><orcidid>https://orcid.org/0000-0001-7692-0039</orcidid><orcidid>https://orcid.org/0000-0002-4909-6694</orcidid><orcidid>https://orcid.org/0000-0003-3235-9221</orcidid></search><sort><creationdate>20210801</creationdate><title>Coloring Properties of Mixed Cycloids</title><author>Dósa, György ; Newman, Nicholas ; Tuza, Zsolt ; Voloshin, Vitaly</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c364t-9de8a45e6c9e7687465eea97f26a2a18929240198ee4884de8bfd422a811eb883</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Algorithms</topic><topic>Apexes</topic><topic>circular hypergraph</topic><topic>Color</topic><topic>coloring</topic><topic>Cycloids</topic><topic>Graph coloring</topic><topic>Graph theory</topic><topic>Graphs</topic><topic>mixed hypergraph</topic><topic>Upper bounds</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Dósa, György</creatorcontrib><creatorcontrib>Newman, Nicholas</creatorcontrib><creatorcontrib>Tuza, Zsolt</creatorcontrib><creatorcontrib>Voloshin, Vitaly</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Engineered Materials Abstracts</collection><collection>Solid State and Superconductivity Abstracts</collection><collection>METADEX</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Aerospace Database</collection><collection>SciTech Premium Collection</collection><collection>Materials Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Engineering Database</collection><collection>ProQuest - Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection><collection>Directory of Open Access Journals (Open Access)</collection><jtitle>Symmetry (Basel)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Dósa, György</au><au>Newman, Nicholas</au><au>Tuza, Zsolt</au><au>Voloshin, Vitaly</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Coloring Properties of Mixed Cycloids</atitle><jtitle>Symmetry (Basel)</jtitle><date>2021-08-01</date><risdate>2021</risdate><volume>13</volume><issue>8</issue><spage>1539</spage><pages>1539-</pages><issn>2073-8994</issn><eissn>2073-8994</eissn><abstract>In this paper, we investigate partitions of highly symmetrical discrete structures called cycloids. In general, a mixed hypergraph has two types of hyperedges. The vertices are colored in such a way that each C-edge has two vertices of the same color, and each D-edge has two vertices of distinct colors. In our case, a mixed cycloid is a mixed hypergraph whose vertices can be arranged in a cyclic order, and every consecutive p vertices form a C-edge, and every consecutive q vertices form a D-edge in the ordering. We completely determine the maximum number of colors that can be used for any p≥3 and any q≥2. We also develop an algorithm that generates a coloring with any number of colors between the minimum and maximum. Finally, we discuss the colorings of mixed cycloids when the maximum number of colors coincides with its upper bound, which is the largest cardinality of a set of vertices containing no C-edge.</abstract><cop>Basel</cop><pub>MDPI AG</pub><doi>10.3390/sym13081539</doi><orcidid>https://orcid.org/0000-0001-7692-0039</orcidid><orcidid>https://orcid.org/0000-0002-4909-6694</orcidid><orcidid>https://orcid.org/0000-0003-3235-9221</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2073-8994
ispartof Symmetry (Basel), 2021-08, Vol.13 (8), p.1539
issn 2073-8994
2073-8994
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_3e3b6d2f80d44234b8d7d1f4db2a841f
source ProQuest - Publicly Available Content Database
subjects Algorithms
Apexes
circular hypergraph
Color
coloring
Cycloids
Graph coloring
Graph theory
Graphs
mixed hypergraph
Upper bounds
title Coloring Properties of Mixed Cycloids
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T13%3A18%3A49IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Coloring%20Properties%20of%20Mixed%20Cycloids&rft.jtitle=Symmetry%20(Basel)&rft.au=D%C3%B3sa,%20Gy%C3%B6rgy&rft.date=2021-08-01&rft.volume=13&rft.issue=8&rft.spage=1539&rft.pages=1539-&rft.issn=2073-8994&rft.eissn=2073-8994&rft_id=info:doi/10.3390/sym13081539&rft_dat=%3Cproquest_doaj_%3E2565715215%3C/proquest_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c364t-9de8a45e6c9e7687465eea97f26a2a18929240198ee4884de8bfd422a811eb883%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2565715215&rft_id=info:pmid/&rfr_iscdi=true